/**
 * @param {number[][]} triangle
 * @return {number}
 */
export var minimumTotal = function (triangle) {
  const dp = [[triangle[0][0]]]
  for (let i = 1; i < triangle.length; i++) {
    dp[i] = []
    const row = triangle[i]
    for (let j = 0; j < row.length; j++) {
      if (j === 0) {
        dp[i][j] = dp[i - 1][j] + row[j]
      } else if (j === row.length - 1) {
        dp[i][j] = dp[i - 1][j - 1] + row[j]
      } else {
        dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + row[j]
      }
    }
  }
  return dp[triangle.length - 1].reduce((a, b) => Math.min(a, b))
}
